distribut comput field comput scienc studi distribut system distribut system consist multipl autonom comput commun comput network comput interact order achiev common goal comput program run distribut system call distribut program distribut program process write program distribut comput refer distribut system solv comput problem distribut comput problem divid task solv comput content hide introduct parallel distribut comput histori applic theoret foundat model complex measur problem properti distribut system architectur note refer read extern link edit introductionth word distribut term distribut system distribut program distribut algorithm origin refer comput network individu comput physic distribut geograph area term nowadai wider sens refer autonom process run physic comput interact messag pass singl definit distribut system defin properti commonli autonom comput entiti local memori entiti commun messag pass articl comput entiti call comput node distribut system common goal solv larg comput problem altern comput user individu purpos distribut system coordin share resourc provid commun servic user typic properti distribut system includ system toler failur individu comput structur system network topolog network latenc number comput advanc system consist kind comput network link system chang execut distribut program comput limit incomplet view system comput part input distribut system parallel system edit parallel distribut comput distribut system network comput oper processor term concurr comput parallel comput distribut comput lot overlap clear distinct exist system characteris parallel distribut processor typic distribut system run concurr parallel parallel comput tightli coupl form distribut comput distribut comput loos coupl form parallel comput roughli classifi concurr system parallel distribut criteria parallel comput processor access share memori share memori exchang inform processor distribut comput processor privat memori distribut memori inform exchang pass messag processor figur illustr differ distribut parallel system figur schemat view typic distribut system usual system repres graph node vertex comput edg line node commun link figur show distribut system detail comput local memori inform exchang pass messag node commun link figur show parallel system processor direct access share memori situat complic tradit term parallel distribut algorithm match definit parallel distribut system section theoret foundat detail discuss rule thumb high perform parallel comput share memori multiprocessor parallel algorithm coordin larg scale distribut system distribut algorithm edit historyth concurr process commun messag pass root oper system architectur studi widespread distribut system local area network ethernet invent arpanet predecessor internet introduc late arpanet mail invent earli mail success applic arpanet earliest larg scale distribut applic addit arpanet successor internet earli worldwid comput network includ usenet fidonet support distribut discuss system studi distribut comput branch comput scienc late earli confer field symposium principl distribut comput podc date back european counterpart intern symposium distribut comput disc held edit applicationsther main reason distribut system distribut comput natur applic requir commun network connect comput data produc physic locat need locat case singl comput principl distribut system benefici practic reason cost effici obtain desir level perform cluster low end comput comparison singl high end comput distribut system reliabl distribut system singl point failur distribut system easier expand manag monolith uniprocessor system exampl distribut system applic distribut comput includ telecommun network telephon network cellular network comput network internet wireless sensor network rout algorithm network applic world wide web peer peer network massiv multiplay onlin game virtual realiti commun distribut databas distribut databas manag system network file system distribut inform process system bank system airlin reserv system real time process control aircraft control system industri control system parallel comput scientif comput includ cluster comput grid comput volunt comput project list distribut comput project distribut render comput graphic edit theoret foundationsmain articl distribut algorithm edit modelsmani task autom comput question answer type question comput produc answer theoret comput scienc task call comput problem formal comput problem consist instanc solut instanc instanc question solut desir answer question theoret comput scienc seek understand comput problem solv comput comput theori effici comput complex theori tradition problem solv comput design algorithm produc correct solut instanc algorithm implement comput program run gener purpos comput program read problem instanc input perform comput produc solut output formal random access machin univers ture machin abstract model sequenti gener purpos comput execut algorithm field concurr distribut comput studi similar question case multipl comput comput execut network interact process comput problem solv network effici obviou meant solv problem case concurr distribut system task algorithm design concurr distribut equival sequenti gener purpos comput discuss focuss case multipl comput issu concurr process run singl comput viewpoint commonli parallel algorithm share memori model comput access share memori algorithm design choos program execut comput theoret model parallel random access machin pram classic pram model assum synchron access share memori model closer behavior real world multiprocessor machin take account machin instruct compar swap ca asynchron share memori wide bodi work model summari found literatur parallel algorithm messag pass model algorithm design choos structur network program execut comput model boolean circuit sort network boolean circuit comput network gate comput run extrem simpl comput program similarli sort network comput network compar comput distribut algorithm messag pass model algorithm design choos comput program comput run program system work correctli structur network commonli model graph finit state machin node case distribut algorithm comput problem typic relat graph graph describ structur comput network problem instanc illustr edit exampleconsid comput problem find color graph field approach central algorithm graph encod string string input comput comput program find color graph encod color string output result parallel algorithm graph encod string multipl comput access string parallel comput focu part graph produc colour part main focu high perform comput exploit process power multipl comput parallel distribut algorithm graph structur comput network comput node commun link edg initi comput neighbour graph comput exchang messag discov structur comput produc colour output main focu coordin oper arbitrari distribut system field parallel algorithm focu field distribut algorithm lot interact field cole vishkin algorithm graph colour origin present parallel algorithm techniqu directli distribut algorithm parallel algorithm implement parallel system share memori distribut system messag pass tradit boundari parallel distribut algorithm choos suitabl network run network lie place boundari parallel distribut system share memori messag pass edit complex measuresin parallel algorithm resourc addit time space number comput trade run time number comput problem solv faster comput run parallel speedup decis problem solv polylogarithm time polynomi number processor problem class nc class nc defin equal pram formal boolean circuit pram machin simul boolean circuit effici vice versa analysi distribut algorithm attent paid commun oper comput step simplest model distribut comput synchron system node oper lockstep fashion commun round node parallel receiv latest messag neighbour perform arbitrari local comput send messag neighbour system central complex measur number synchron commun round requir complet task complex measur close relat diamet network diamet network hand comput problem solv trivial synchron distribut system approxim commun round simpli gather inform locat round solv problem inform node solut round hand run time algorithm smaller commun round node network produc output possibl obtain inform distant part network word node make global consist decis base inform local neighbourhood distribut algorithm run time smaller round understand problem solv algorithm central research question field commonli measur total number bit transmit network cf commun complex edit problemstradit comput problem perspect question comput distribut system process question produc answer stop problem system stop exampl problem includ dine philosoph problem similar mutual exclus problem problem distribut system suppos continu coordin share resourc conflict deadlock occur fundament challeng uniqu distribut comput challeng relat fault toler exampl relat problem includ consensu problem byzantin fault toler stabilis lot research focus understand asynchron natur distribut system synchron run synchron algorithm asynchron system logic clock provid causal happen order event clock synchron algorithm provid global consist physic time stamp edit properti distribut systemsso focu design distribut system solv problem complementari research problem studi properti distribut system halt problem analog field centralis comput comput program task decid halt run forev halt problem undecid gener case natur understand behaviour comput network hard understand behaviour comput interest special case decid reason behaviour network finit state machin tell network interact asynchron determinist finit state machin reach deadlock problem pspace complet decid effici centralis parallel distribut algorithm solv problem case larg network edit architecturesvari hardwar softwar architectur distribut comput lower level interconnect multipl cpu sort network network print circuit board made loos coupl devic cabl higher level interconnect process run cpu sort commun system distribut program typic fall basic architectur categori client server tier architectur tier architectur distribut object loos coupl tight coupl client server smart client code contact server data format displai user input client commit back server repres perman chang tier architectur tier system move client intellig middl tier stateless client simplifi applic deploy web applic tier tier architectur tier refer typic web applic forward request enterpris servic type applic respons success applic server tightli coupl cluster refer typic cluster machin close work run share process parallel task subdivid part made individu put back make final result peer peer architectur special machin machin provid servic manag network resourc respons uniformli divid machin peer peer serv client server space base refer infrastructur creat illus virtual singl address space data transpar replic applic decoupl time space refer achiev basic aspect distribut comput architectur method commun coordin work concurr process messag pass protocol process commun directli typic master slave relationship altern databas centric architectur enabl distribut comput form direct inter process commun util share databas 